Breve introducción a la aritmética modular

La operación módulo, para dos números enteros $a$ y $b$, se define como $a \mod b := \text{residuo}( a \div b)$, entendiendo la división como la división euclídea: dados dos números enteros $a$ y $b\neq 0$, entonces existen otros dos números enteros, únicos, $q,r$, tales que $a=b\cdot q+r \wedge 0\le r \lt |b|$ . Así por ejemplo, $15 \mod 7 =1$, ya que $8=7\cdot 2+1$; $-6 \mod 7 = 1$ ya que $-6=7\cdot (-1) +1$.

Decimos que dados dos números enteros $m$ y $n$ son congruentes entre sí con respecto a un determinado número entero $p$, y lo escribimos $m \equiv n (\mod p)$ si $m \mod p = n \mod p$, esto es, si las divisiones euclídeas $m \div p$ y $n \div p$ tienen el mismo resto. Así, por ejemplo, $15 \equiv 22 (\mod 7)$ ya que $15 \mod 7 = 1 = 22 \mod 7$. Tambien podemos decir, entre otras muchas cosas al rspecto, que $15 \equiv -6 (\mod 7)$ ya que $15 \mod 7 = 1 = -6 \mod 7$. Démonos cuenta que fácilmente podemos ir escribiendo infinitos enteros congruentes con $15$ sumando (o restando) siete unidades —y lo mismo con cualquier otro número que sepamos que es congruente con $14$ módulo $7$—; así, si tomamos, por ejemplo, $15$, encontramos que: $22,29,36,\ldots$ y $8,1,-6.-13\,\ldots$ son números congruentes con $15$ módulo $7$.

Esta operación módulo es muy importante en la teoría elemental de números (o matemática discreta): es necesaria en los cálculos con congruencias, en la resolución de ecuaciones diofánticas (ecuaciones con coeficientes enteros con solución en el conjunto de los números enteros) y, también, juegan un papel de importantísimo para entender y probar proposiciones en teoría de números (matemática discreta). Como ejemplo práctico podemos subrayar que la matemática discreta es fundamental en el diseño de algoritmos y en programación.

Muchas calculadoras científicas incorporan esta operación, y la secuencia de tecleo suele ser (para el ejemplo que comento): [15 $\rightarrow$ mod $\rightarrow$ 7 $\rightarrow$ = (o EXE)], presentándose el resultado, $1$, en pantalla.

La congruencia cumple dos propiedades básicas. Si $a_1 \equiv a_2 (\mod p)$ y $b_1 \equiv b_2 (\mod p)$, entonces:

• $a_1+b_1 \equiv a_2 + b_2 \,(\mod p)$
• $a_{1}\cdot b_{1} \equiv a_{2} \cdot b_{2}\, (\mod p)$

Por ejemplo, $26 \equiv 19 (\mod 7)$, ya que $26 \mod 7 = 5 = 19 \mod 7$, y $27 \equiv 13 (\mod 7)$ puesto que $27 \mod 7 = 6 = 13 \mod 7$. Por tanto:

• $26+27 \equiv 19+13 (\mod 7)$, esto es, $53 \equiv 32 (\mod 7)$; en efecto: $53 \mod 7 = 4 = 32 \mod 7$
• $26\cdot 27 \equiv 19\cdot 13 (\mod 7)$, esto es, $702 \equiv 247 (\mod 7)$; en efecto: $702 \mod 7 = 2 = 247 \mod 7$

$\diamond$